package T2;

import java.util.Scanner;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 马拉圈
 * Date: 2023-03-31
 * Time: 14:42
 */
public class Day11 {


    public static void findRoute(Stack<Integer> stack, int root, int foundNum) {
        if(root > foundNum) {
            return;
        }else {
            stack.push(root);
            findRoute(stack, 2 * root, foundNum);
            if(!stack.isEmpty() && stack.peek() == foundNum) {
                return;
            }
            findRoute(stack, 2 * root + 1, foundNum);
            if(!stack.isEmpty() && stack.peek() != foundNum) {
                stack.pop();
            }
        }
    }

    public static int getLCA(int a, int b) {

        try {
            Stack<Integer> stack1 = new Stack<>();
            Stack<Integer> stack2 = new Stack<>();

            findRoute(stack1, 1, a);
            findRoute(stack2, 1, b);
            int len1 = stack1.size();
            int len2 = stack2.size();
            while(len1 < len2) {
                len2--;
                stack2.pop();
            }
            while(len1 > len2) {
                len1--;
                stack1.pop();
            }
            while(!stack1.isEmpty()) {
                int number1 = stack1.pop();
                int number2 = stack2.pop();
                if(number1 == number2) {
                    return number1;
                }
            }
        } catch (IndexOutOfBoundsException e) {
            e.printStackTrace();
        }
        return 1;
    }

    public static void main(String[] args) {
        System.out.println(getLCA(0, 53));
    }

    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt()) {
            Stack<Integer> stack1 = new Stack<>();
            Stack<Integer> stack2 = new Stack<>();
            int root1 = scanner.nextInt();
            int root2 = scanner.nextInt();
            System.out.println(getLCA(root1, root2));
        }
    }




    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt()) {
            int value = scanner.nextInt();
            int max = 0;
            int count = 0;
            while(value != 0) {
                int num = value % 2;
                value /= 2;
                if(num == 1) {
                    count++;
                }else {
                    if(count > max) {
                        max = count;
                    }
                    count = 0;
                }
                if(value == 0) {
                    if(count > max) {
                        max = count;
                    }
                }
            }
            System.out.println(max);
        }
    }
}
